﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0195_FindLongestChain : IAlgorithm
    {
        // 646. 最长数对链

        // 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
        // 现在，我们定义一种跟随关系，当且仅当 b<c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
        // 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

        // 提示：
        //  给出数对的个数在[1, 1000] 范围内。

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public int FindLongestChain(int[][] pairs)
        {
            int curr = int.MinValue, res = 0;
            Array.Sort(pairs, (a, b) => a[1] - b[1]);
            foreach (int[] p in pairs)
            {
                if (curr < p[0])
                {
                    curr = p[1];
                    res++;
                }
            }
            return res;
        }
    }
}
